/*
leetcode 274: https://leetcode.cn/problems/h-index/?envType=study-plan-v2&envId=top-interview-150
题目描述：
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，
并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

 

示例 1：
输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：
输入：citations = [1,3,1]
输出：1
 

提示：
n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

解题思路：
1. 逆序排序法：先排序，然后逆序比较引用数与 h 指数大小，大于则 h 指数+1，

*/
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int h = 0, i = citations.size() - 1;
        while (i >= 0 && citations[i] > h) {
            h++;
            i--;
        }
        return h;
    }
};
/*
citations = 3 0 1 6 5
 
排序：0 1 3 5 6
h=0 i=4

while i>=0 &citations[i] > h 6>0
    h++ h=1
    i-- i=3

while i>=0 &citations[i] > h 5>1
    h++ h=2
    i-- i=2

while i>=0 &citations[i] > h 3>2
    h++ h=3
    i-- i=1

while i>=0 &citations[i] > h 1>3 不成立

*/

int main() {
    vector <int> citations = {3, 0, 1, 6, 5};
     Solution s;
     int h_index =  s.hIndex(citations);
     cout << "h_index: " << h_index << endl;

    return 0;
}
